'''
希尔排序: 也是一种插入排序,它通过设置一个间隔，对同样间隔的数的集合进行插入排序，此数集合中的元素移位的长度是以间隔的长度为准，这样就实现了大步位移。但是最后需要对元素集合进行一次直接插入排序，所以最后的间隔一定是1。但是这个间隔怎么确定，这是个数学难题，至今没有解答
时间复杂度:最坏 O()n²
稳定性:不稳定
'''


def shell_sort(list):
    n = len(list)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            idx = i
            while idx > 0:
                if list[idx] < list[idx - gap]:
                    list[idx], li[idx - gap] = list[idx - gap], list[idx]
                    idx -= gap
                else:
                    break
        gap = gap // 2


if __name__ == '__main__':
    li = [31, 232, 65, 12, 928, 54, 21, 100, 4]
    shell_sort(li)
    print(li)
